package com.hanxiaozhang.sort;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈归并排序〉
 *
 * @author hanxinghua
 * @create 2021/9/10
 * @since 1.0.0
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] array1 = {1, 3,  5,  22, 4};
        mergeSort1(array1);
        System.out.println(Arrays.toString(array1));

        int[] array2 = {1, 3,  5,  22, 4};
        mergeSort2(array2);
        System.out.println(Arrays.toString(array2));

    }



    /**
     * 非递归方法实现
     * 流程：第一次：先设置mergeSize大小为1，从数组左侧找出第一个左右分组，进行比较，然后在去寻找下一个左右分组，以此类推，知道最后一个。
     * 第二次：先设置mergeSize大小为2，从数组左侧找出第一个左右分组，进行比较，然后在去寻找下一个左右分组，以此类推，知道最后一个。
     * 第三次：以此来推
     *
     * 
     * @param array
     */
    public static void mergeSort2(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int N = array.length;
        // 分组大小，即左组是1 ，右组是1
        int mergeSize = 1;
        while (mergeSize < N) {
            // 左边界是0
            int L = 0;
            while (L < N) {
                // 中间位置
                int M = L + mergeSize - 1;
                // 中间位置大于数组大小，结束循环，即此mergeSize的分组比较，已经全部完成了。
                if (M >= N) {
                    break;
                }
                // 确定左边界位置
                int R = Math.min(M + mergeSize, N - 1);
                // 比较
                merge(array, L, M, R);
                // 右边界+1变成左边界，比较下一组
                L = R + 1;
            }
            // 如果mergeSize大于数组长度一半，即已经完成排序，还可以防止数组个数过大，溢出
            if (mergeSize > N / 2) {
                break;
            }
            // 分组大小 * 2
            mergeSize <<= 1;
        }
    }
    

    /**
     * 递归方法实现
     *
     * 一直两分分组到不能分组，每次都调用merge方法
     *
     *
     * @param array
     */
    public static void mergeSort1(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        process(array, 0, array.length - 1);
    }

    /**
     * 数组索引中间数，递归分成左右两组（一直分到，每组有一个或两个），
     * 两组merge比较。
     *
     * @param array
     * @param L
     * @param R
     */
    public static void process(int[] array, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(array, L, mid);
        process(array, mid + 1, R);
        merge(array, L, mid, R);
    }

    /**
     * 归并比较
     *
     * @param array
     * @param L
     * @param M
     * @param R
     */
    public static void merge(int[] array, int L, int M, int R) {
        // 帮助数组，容量 L-R范围数组原始个数
        int[] help = new int[R - L + 1];
        int index = 0;
        // 左数组的起点
        int p1 = L;
        // 右数组的起点
        int p2 = M + 1;
        // 循环比较左右数组中最大，存入帮助数组，保证不越界 ==> 只有越界才跳出循环，但只会存在一个数组越界
        while (p1 <= M && p2 <= R) {
            // p1小于等于p2，存入p1，否则存入p2。（谁小拷贝谁）
            help[index++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
        }
        // 如果右数组越界，即左侧数组有元素，将左数组剩余元素存入帮助数组
        while (p1 <= M) {
            help[index++] = array[p1++];
        }
        // 如果左数组越界，即右侧数组有元素，将右数组存剩余元素入帮助数组
        while (p2 <= R) {
            help[index++] = array[p2++];
        }
        // 替换
        for (int i = 0; i < help.length; i++) {
            array[L + i] = help[i];
        }
    }

}
